package main

/*
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
*/

import "fmt"

type Node struct {
	Val       int
	Neighbors []*Node
}

func (n *Node) Walk() {
	visited := make(map[int]bool)
	n.walk(visited)
}

func (n *Node) walk(visited map[int]bool) {
	if n == nil {
		return
	}
	fmt.Printf("%d:", n.Val)
	visited[n.Val] = true
	for _, neighbour := range n.Neighbors {
		fmt.Print(neighbour.Val)
	}
	fmt.Println()
	for _, neighbour := range n.Neighbors {
		if visited[neighbour.Val] {
			continue
		}
		neighbour.walk(visited)
	}
}

func cloneGraph(node *Node) *Node {
	if node == nil {
		return nil
	}
	visited := make(map[int]*Node) // 邻居字典，如果已经克隆了可以直接取出
	return dfsClone(node, visited)
}

func dfsClone(node *Node, visited map[int]*Node) *Node {
	// 如果已经克隆，直接退出即可
	if _, exists := visited[node.Val]; exists {
		return nil
	}
	// 否则进行克隆
	newNode := &Node{Val: node.Val}
	visited[node.Val] = newNode
	var neighbourArr []*Node
	// 克隆邻居列表
	for _, neighbour := range node.Neighbors {
		// 如果邻居已经克隆了，可以直接取出地址赋值过来
		if n, exists := visited[neighbour.Val]; exists {
			neighbourArr = append(neighbourArr, n)
			continue
		}
		neighbourArr = append(neighbourArr, dfsClone(neighbour, visited))
	}
	newNode.Neighbors = neighbourArr
	return newNode
}

func cloneGraph2(node *Node) *Node {
	return bfsClone(node)
}

func bfsClone(node *Node) (newNode *Node) {
	visited := make(map[int]*Node)
	var queue []*Node
	queue = append(queue, node) //因为要取出邻居信息，所以入队原节点，当然也可以如对一个结构体，保存原节点和新复制节点
	newNode = &Node{Val: node.Val}
	visited[node.Val] = newNode // 访问数组保存新节点信息，用于查询出来更新邻居，如果入队采用了结构体，这里则不用再存新节点信息
	for len(queue) != 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			head := queue[0]
			queue = queue[1:]
			newHead := visited[head.Val]               // 取出新节点正准备更新
			for _, neighbour := range head.Neighbors { // 取出原节点的邻居准备更新
				if n, exists := visited[neighbour.Val]; exists {
					newHead.Neighbors = append(newHead.Neighbors, n)
					continue
				}
				newNeighbour := &Node{Val: neighbour.Val}
				newHead.Neighbors = append(newHead.Neighbors, newNeighbour)
				visited[neighbour.Val] = newNeighbour
				queue = append(queue, neighbour)
			}
		}
	}
	return newNode
}

func main() {
	node1 := Node{Val: 1}
	node2 := Node{Val: 2}
	nodde3 := Node{Val: 3}
	nodde4 := Node{Val: 4}
	node1.Neighbors = []*Node{&node2, &nodde4}
	node2.Neighbors = []*Node{&node1, &nodde3}
	nodde3.Neighbors = []*Node{&node2, &nodde4}
	nodde4.Neighbors = []*Node{&node1, &nodde3}
	node1.Walk()
	fmt.Println("==============")
	newNode := cloneGraph(&node1)
	// fmt.Println(newNode)
	newNode.Walk()
	fmt.Println("==============")
	bfsNewNode := cloneGraph2(&node1)
	bfsNewNode.Walk()
}
